package com.dyz.leetcode._20_dynamicProgramming.knapsack;

public class knapsack02 {
    private int[] w;
    private int[] v;

    private int maxValue = 0;

    public int knapsack(int[] w, int[] v, int C) {
        this.w = w;
        this.v = v;
        dfs(-1, C, 0);
        return maxValue;
    }

    private void dfs(int index, int c, int currValue) {
        // 处理当前节点（父节点）
        maxValue = Math.max(maxValue, currValue);

        // 从 index 开始是为了控制顺序
        for (int i = index; i < w.length; i++) {
            // 处理子节点
            int childIndex = i + 1;

            if (childIndex == w.length) {continue;}
            if (c < w[childIndex]) {continue;}

            dfs(childIndex, c - w[childIndex], currValue + v[childIndex]);
        }
    }
}
